package com.nowcoder.Offer.Heap;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * 数据流的中位数
 */
public class medianOfStream {

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a , b) -> b - a);
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    int count = 0;

    public void Insert(Integer num) {
        if((count & 0x1) == 0){
           maxHeap.offer(num);
           minHeap.offer(maxHeap.poll());
        }else{
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
        count++;

    }



    public Double GetMedian() {
        return count % 2 == 0 ?
                new Double(minHeap.peek() + maxHeap.peek()) / 2 :
                new Double(minHeap.peek());
    }

    @Test
    public void test(){
        medianOfStream medianOfStream1 = new medianOfStream();
        int[] arr = {5,2,3,4,1,6,7,0,8};
        for(int i = 0; i<arr.length; i++){
            medianOfStream1.Insert(arr[i]);
            System.out.println(medianOfStream1.GetMedian());
        }
    }
}
















